package com.heima.algorithm.sort;

/**
 * <h3>计数排序</h3>
 * <ol>
 *     <li>找到最大值和最小值，创建一个最大值 - 最小值 + 1大小的count数组</li>
 *     <li>当前数组元素 - 最小值就是count数组中的索引位置，count数组的值为出现次数</li>
 *     <li>遍历count数组，生成对应的遍历好的数组</li>
 * </ol>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/5 23:58
 */
public class CountingSort {
    //（1）非比较排序算法
    //（2）时间复杂度：O(N + K)，空间复杂度：O(N + K)，N为数组长度，K为count数组长度，稳定：是

    /**
     * 计数排序
     * @param arr 待排序数组
     */
    public static void countingSort(int[] arr){
        int max = arr[0]; // 记录最大值
        int min = arr[0]; // 记录最小值
        // 找到最大值和最小值
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
            if (arr[i] < min){
                min = arr[i];
            }
        }
        // 创建count数组
        int[] count = new int[max - min + 1];
        // 统计每个元素出现的次数
        for (int i : arr) {
            count[i - min]++;
        }
        // 遍历count数组，生成排序好的数组
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            for (int j = 0; j < count[i]; j++) {
                arr[index++] = i + min;
            }
        }
    }
}
